/**
 * https://leetcode.cn/problems/next-greater-element-i/
 */
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const ans: number[] = [];
  // 1. 为 nums2 构建右边第一个比自己大的
  const stack: number[] = [];
  const map = new Map<number, number>();
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length && stack[stack.length - 1] < nums2[i]) {
      //   map[stack.pop()!] = nums2[i];
      map.set(stack.pop()!, nums2[i]);
    }
    stack.push(nums2[i]);
  }

  // 2. 构建结果
  for (let num of nums1) {
    const largeNum = map.get(num);
    if (largeNum) {
      ans.push(largeNum);
    } else {
      ans.push(-1);
    }
  }

  return ans;
}

function nextGreaterElement2(nums1: number[], nums2: number[]): number[] {
    const ans: number[] = [];
    // 1. 为 nums2 构建右边第一个比自己大的
    const stack: number[] = [];
    const map: Record<number, number> = {};
    for (let i = 0; i < nums2.length; i++) {
      while (stack.length && stack[stack.length - 1] < nums2[i]) {
        map[stack.pop()!] = nums2[i];
      }
      stack.push(nums2[i]);
    }
  
    // 2. 构建结果
    for (let num of nums1) {
      const largeNum = map[num];
      if (largeNum) {
        ans.push(largeNum);
      } else {
        ans.push(-1);
      }
    }
  
    return ans;
  }
// [1,3,4,2] => {1: 1, 3: 2, 4: -1, 2: -1}
// console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]));
